This invention relates to memory systems and, in particular, to memory systems for storing block structured data. It finds application where non-volatile memory cells are used as the storage medium. The particular type of non-volatile memory cells used in this invention are memory cells which do not allow erasure of individual cells but allow erasure of blocks of memory cells. Different memory cells, such as FLASH EPROM cells, chalcogenide memory cells, and ferro-optic cells may be used.
Many common memory storage devices for computers are based on rotating storage media such as the magnetic disk drive. Rotating storage media have, however, a few disadvantages. They require comparatively large amounts of power because they consist of rotating platters. They are comparatively slow to read from and write to because of the seek latency (the time taken to move the head to the correct location) and the rotational latency (the time taken to locate the correct part of a track). Magnetic disks are also comparatively heavy and not very robust (they are sensitive to being knocked). In contrast, semiconductor memory is lightweight, robust, consumes very little power, and is fast in operation. For these reasons it is desirable to use a solid state equivalent of the magnetic disk. The particular semiconductor chosen as the solid state memory is preferably high density, non-volatile, and has low cost per bit. This makes FLASH memory an ideal candidate.
There are many prior art references to the use of FLASH memory as the storage medium for a solid state disk drive. These references include the following patents: EP 0 392 895, EP 0 424 191, EP 0 522 780, EP 0 597 706, EP 0 617 363, EP 0 618 535, EP 0 619 541, GB 2 251 323, WO 93 02418, WO 94 19746, WO 94 20906, WO 94 23369, WO 94 23432, WO 95 14272, WO 95 10083, U.S. Pat. No. 4,511,964, WO 84 00628, WO 95 10083, WO 95 14272. Many of these references have certain features in common. For example, most references disclose the use of a table for converting the logical address from the host computer (usually in CHS--cylinder, head and sector-format) to a physical address in the FLASH memory or to an intermediate address which will be used for generating the physical address in FLASH memory. Most references also have some means for ensuring that one block is not written to substantially more times than another block. A third common feature in FLASH solid state disk emulators is a buffer for increasing the write speed to the semiconductor. The buffer is usually made of some fast memory such as SRAM (Static Random Access Memory).
Any solid state disk emulation system which uses FLASH memory as the storage medium must also have some method of controlling the erasure and writing of the cells. The reason for this is that the cells take a comparatively long time to erase and a cell can only be written to once before it needs to be erased. The present invention uses an algorithm which may be used in a solid state disk emulating system for controlling the writing and erasure of memory cells.
EP 0 522 780 describes a control method for a solid state disk which uses a memory managing table recording the number of times each cell has been erased, the status of each memory block and a buffer to hold data which is to be written to memory. The method involves copying sectors which are to be erased to another block before erasing the initial block.
EP 0 392 895 relates to the use of a cache memory for buffering writes to the FLASH memory to increase the speed of operation of the memory. The memory system in that disclosure uses means to determine "the time since each data file was last written". It also relates to correcting for errors and defect substitution, but these were the subject of divisional applications which are discussed below.
EP 0 618 535 relates to a solid state disk emulator which has defect substitution.
EP 0 617 363 relates to a method of correcting for defective cells in a FLASH memory by using pointers to point from the defective locations in the memory to the spare locations.
EP 0 424 191 relates to a method of storing sequential data in a memory which is accessible in a prescribed order. Defects in the memory are stored in an ordered directory so that these defective locations are skipped when the memory is being written to.
EP 0 619 541 provides a solid state disk emulating system which allows random access from a central processing unit. It also measures the erasure count for each block of memory so that a block can be avoided if it has been written to a large number of times.
EP 0 597 706 discloses a solid state peripheral storage device which uses a MAP ROM to map the logical sector address provided by the host to a physical address in the semiconductor memory. The addresses of any bad sectors in semiconductor memory are recorded in the MAP ROM. A microsequencer is used to control the mapping.
GB 2 251 323 describes a disk emulation system for FLASH memory. The clean up operation described in that disclosure is only automatic in the sense that it happens as a background task when certain conditions are met. Either the least cycled block is erased or the block with the highest number of deleted sectors is erased. This gives rise to an essentially random block selection for erasure.
WO 94 20906 discloses a FLASH file system which is used to emulate the operation of a disk drive. It uses a block allocation map to store information on the blocks in FLASH memory that can be written to. When a block is to be updated the allocation map is scanned until a free block is located. A transfer unit is used to facilitate memory reclaiming of the system. The transfer unit is an unwritten erased block of memory. The active (currently valid) data from a block of memory that contains old data (the old block) is written to the same locations in the transfer unit (the new block) and the old block is erased. The old block then becomes the transfer unit.
WO 94 23432 discloses a FLASH memory mass storage architecture. Erase cycles are avoided by programming altered data file into an empty mass storage block. Periodically the storage is cleaned up with a multi-sector erase. A counter is used to ensure that no block is erased more than a maximum number of times.
WO 94 23369 discloses a FLASH memory mass storage architecture which is very similar to that disclosed in WO 94 23432. Both disclosures are by the same applicant.
WO 94 19746 discloses a FLASH solid state drive which stores two bytes at a time. Each time a sector is written into FLASH memory a header is also written with it. If an older version of that sector exists in the memory then it is marked as invalid. When storage space dips below a certain threshold then a clean up operation is performed. Good data from a sector is copied to a buffer, the sector is erased and the good data is copied back to the sector.
WO 84 00628 discloses a method of managing defects in a storage media. The method involves receiving an address from a host, compensating the received address for the number of defective locations below that address, and accessing the compensated address. A sequentially ordered list of defective locations in the storage media is constructed.
WO 95 10083 uses counters to count the number of erase cycles each block has experienced and copies updated versions of data files to new locations. Periodically, blocks are erased to clean up the system. The blocks in the semiconductor memory are sized to conform to commercial hard disk sector sizes.
WO 95 14272 provides a method of generating the correct physical starting address from the number of the logical block to be accessed.